package jjn.round2;

/**
 * @author Jiang Jining
 * @since 2023-05-10 23:31
 */
public class Offer13_MovingCount {
    
    
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        return dfs(m, n, 0, 0, k, visited);
    }
    
    private int dfs(int m, int n, int i, int j, int k, boolean[][] visited) {
        if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || (i / 10 + i % 10 + j / 10 + j % 10) > k) {
            return 0;
        }
        visited[i][j] = true;
        return 1 + dfs(m, n, i + 1, j, k, visited) + dfs(m, n, i - 1, j, k, visited)
                + dfs(m, n, i, j + 1, k, visited) + dfs(m, n, i, j - 1, k, visited);
    }
}
